
assert(LibStub, "AdtHeapMin-1.0 requires LibStub")

local HeapMin, oldminor = LibStub:NewLibrary("AdtHeapMin-1.0", 0)
if not HeapMin then return end
oldminor = oldminor or 0

local storage={}
local Heap_mt = { __index = HeapMin,__metatable="instance AdtHeapMin-1.0" }

function HeapMin:make_heap()
   return setmetatable( {heap={}, size=0}, Heap_mt)
 end

setmetatable(HeapMin, {__call = HeapMin.make_heap,__metatable="class AdtHeapMin-1.0"})
local lchild
local rchild
local temp
function HeapMin:heapify_node(index)
	lchild = self:l_child(index);
	rchild = self:r_child(index);

	if(0 <= lchild and lchild <= self.size + 1 and self.heap[lchild].key < self.heap[index].key) then
		temp = self.heap[lchild];
		self.heap[lchild] = self.heap[index];
		self.heap[lchild].position = lchild;
		self.heap[index] = temp;
		self.heap[index].position = index;
	end

	if(0 <= rchild and rchild <= self.size + 1 and self.heap[rchild].key < self.heap[index].key) then
		temp = self.heap[rchild];
		self.heap[rchild] = self.heap[index];
		self.heap[rchild].position = rchild;
		self.heap[index] = temp;
		self.heap[index].position = index;
	end

end
local return_spot
local new_node
function HeapMin:insert(key, item)

    return_spot = 0;
	if #storage==0 then
		new_node = {key=key,item=item};
	else
		new_node=tremove(storage)
		new_node.key=key
		new_node.item=item
	end

	self.heap[self.size] = new_node;

	return_spot = self:heapify_up(self.size);

	new_node.position = return_spot;

	self.size = self.size + 1;

    return return_spot;

end

function HeapMin:get_min()
	if(self.size > 0) then
    	return self.heap[0].key,self.heap[0].item;
	else
		return nil;
	end
end

function HeapMin:delete_min()
    return self:delete_node(0);
end
function HeapMin:clear_heap( )
	wipe(storage)
	self.heap = {};
	self.size = 0;
end

-- Protected
function HeapMin:delete_node(position)
	if(self.size > 0) then
		tinsert(storage,self.heap[position])
		self.heap[position] = self.heap[self.size - 1];
		self.size = self.size - 1;
		return self:heapify_down( position, self.heap[position]);
	else
		return -1;
	end
end
local min_index
local indexes={}
local array_size

function HeapMin:heapify_down( cur_index, move_content)
    l_child_index = self:l_child(cur_index);
    r_child_index = self:r_child(cur_index);
    min_index = 0;
    --if the node has leaves, find the index of the minimum element, else min_index =  -1
		wipe(indexes)
		array_size = 0;
		
		if(l_child_index ~= -1 and self.heap[l_child_index].key < move_content.key) then
			indexes[array_size] = l_child_index;
			array_size = array_size + 1;
		end
		
		if(r_child_index ~= -1 and self.heap[r_child_index].key < move_content.key) then
			indexes[array_size] = r_child_index;
			array_size = array_size + 1;
		end
		
		if(array_size == 2) then
			if(self.heap[indexes[1] ].key < self.heap[indexes[0] ].key) then
				temp = indexes[1];
				indexes[1] = indexes[0];
				indexes[0] = temp;
			end
		end

		if(array_size == 0)then
			min_index = -1;
		else
			min_index = indexes[0];
		end


    if(min_index ~= -1) then

        self.heap[cur_index] = self.heap[min_index];

        self.heap[cur_index].position = cur_index;
        return self:heapify_down(min_index, move_content);
    else
        self.heap[cur_index] = move_content;
        self.heap[cur_index].position = cur_index;
        return cur_index;
    end
end

local move_content
local parent_index

function HeapMin:heapify_up(cur_index)
    move_content = self.heap[cur_index];
    parent_index = self:parent(cur_index);

    while(parent_index > -1 and self.heap[parent_index].key > move_content.key )do

        self.heap[cur_index] = self.heap[parent_index];

        self.heap[cur_index].position = cur_index;

        cur_index = parent_index;
        parent_index = self:parent(cur_index);

    end

    self.heap[cur_index] = move_content;
    self.heap[cur_index].position = cur_index;

    return cur_index;

end

function HeapMin:parent(position)
    return math.floor(  (position - 1.0) / 2.0)  ;
end

function HeapMin:r_child(position)
    return_position = 2*position + 2;
    if(return_position > self.size - 1)then
        return -1;
    else
        return return_position;
	end
end

function HeapMin:l_child(position)
    return_position = 2*position + 1;
    if(return_position > self.size - 1) then
        return -1;
    else
        return return_position;
	end
end

